|
In bioinformatics, neighbor joining is a bottom-up (agglomerative) clustering method for the creation of phylogenetic trees, created by Naruya Saitou and Masatoshi Nei in 1987.〔(Saitou N, Nei M. "The neighbor-joining method: a new method for reconstructing phylogenetic trees." ''Molecular Biology and Evolution'', volume 4, issue 4, pp. 406-425, July 1987. )〕 Usually used for trees based on DNA or protein sequence data, the algorithm requires knowledge of the distance between each pair of taxa (e.g., species or sequences) to form the tree.〔 〕 == The algorithm == Neighbor joining takes as input a distance matrix specifying the distance between each pair of taxa. The algorithm starts with a completely unresolved tree, whose topology corresponds to that of a star network, and iterates over the following steps until the tree is completely resolved and all branch lengths are known: # Based on the current distance matrix calculate the matrix (defined below). # Find the pair of distinct taxa i and j (i.e. with ) for which has its lowest value. These taxa are joined to a newly created node, which is connected to the central node. In the figure at right, f and g are joined to the new node u. # Calculate the distance from each of the taxa in the pair to this new node. # Calculate the distance from each of the taxa outside of this pair to the new node. # Start the algorithm again, replacing the pair of joined neighbors with the new node and using the distances calculated in the previous step. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Neighbor joining」の詳細全文を読む スポンサード リンク
|